#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2021/6/1 10:18
# @Author  : hqu-jcl
# @Site    : 
# @File    : ParsingTable.py

import termtables as tt
import pandas as pd
import numpy as np
from prettytable import PrettyTable

FIRST = {}
FOLLOW = {}

global buffer

sentences = []

# 集合
global S
N = set()
T = set()

# 改写文法，消除左递归，消除左因子
result_1 = []  # 用来存储消除左递归后的结果
result_2 = []  # 用来存储提取左因子后的结果


def read_grammar():
    """读入文法中所有生成式"""
    grammar = []  # 用来存储输入每个产生式的列表
    num = int(input("请输入文法式子个数："))
    print("请依输入各式子：")
    for i in range(num):
        context_str = input()
        grammar.append(context_str)
    return grammar  # 返回文法产生式的列表


def judge_result(grammar):
    """判断左递归，并返回结果"""
    print("-------------消除左递归-------------")
    print("判断过程：")
    for i in grammar:  # 变量文法中的每一个产生式
        flag = 0  # flag用来标记第i个产生是否存在间接左递归，初始化为0，若存在，则赋值为1
        List = i.split('->')  # 将'->'左右分隔开，分别存入列表
        A = List[0]  # A存储 '→'左边的非终结符
        B = List[1]  # B存储'→'右边的边的非终结符或者终结符
        B = B.split('|')  # 再将B中的多个候选分隔开，B中存储的是多个候选
        for j in B:  # 遍历B中的每个候选
            if j[0] == A:  # 如果B中候选的第一个字符以A中的非终结符开头，则存在直接左递归
                # 提示该式存在左递归的信息
                flag = 1  # 出现左递归标记该式子
                print(i, " 存在左递归！")
                eliminate_left_recursion(A, B)  # 调用消除左递归函数消除左递归
                break
        if flag == 0:
            # 若第i个产生式子不存在左递归
            print(i, " 此生产式子不需要消除递归！")
            result_1.append(i)  # 直接将该式加入到结果列表中


def eliminate_left_recursion(A, B):
    """消除左递归"""
    str1 = A + '->'  # str1用来存储消除左递归后产生的第一个式子
    str2 = A + '\'' + '->'  # str用来存储消除左递归产生的第二个式子
    α = []
    β = []
    # 对候选进行判断划分到α和β中
    for i in B:
        if i[0] != A:
            β.append(i)
        else:
            α.append(i.split(A)[1])
    if len(β) == 0:
        str1 += A + '\''
    else:
        for each in β:
            str1 += each + A + '\'' + '|'
    for each in α:
        str2 += each + A + '\'' + '|'
    str1 = str1.strip('|')  # 去除末尾的|符号
    str2 += 'ε'  # 在末尾加ε
    # 将消除直接左递归后的结果加入结果列表中
    result_1.append(str1)
    result_1.append(str2)


def get_left_factor(result):
    """提取左因子"""
    print("-------------提取左因子-------------")
    print("判断过程：")
    for i in result:
        depart = i.split('->')
        select = depart[1].split('|')  # 候选项列表
        if len(select) == 1:  # 候选项数为1时，不需要提取左因子，退出循环即可
            print(i, " 此生产式子不需要提取左因子！")
            result_2.append(i)

            continue
        else:  # 否则需要提取左因子
            # 先按照首字母将列表各元素分类
            s = set()
            d = dict()
            for j in select:
                s.add(j[0])  # 遍历各个候选将首字母放入集合中，注意会去重
            for k in s:  # 遍历首字母集合，把它们当作字典的键值
                d.setdefault(k, [])
            for j in select:
                d[j[0]].append(j)  # 将具有相同首字母前缀放到自字典的一个key中

            # 对列表中各元素进行最大前缀的提取
            for value_list in d.values():  # 遍历每一个具有相同首字母的候选值，提取他们的公共最长前缀
                if len(value_list) == 1:  # 如果首字母相同的候选只有一个，不需要提取左因子
                    result_2.append(i)
                    print(i, " 此生产式子不需要提取左因子！")
                    break
                else:
                    print(i, " 此生产式子需要提取左因子！")
                    s_min = min(value_list)
                    s_max = max(value_list)
                    longest_common_prefix = ''
                    for index, value in enumerate(s_min):
                        if value != s_max[index]:  # 匹配到一个不相等的字符
                            longest_common_prefix = s_min[:index]  # 记录最大公共前缀
                            break
                    # print("最大公共前缀：", longest_common_prefix)
                    result_2.append(depart[0] + '→' + longest_common_prefix + depart[0] + '\'')
                    x = ""
                    for k in value_list:
                        x += k.replace(longest_common_prefix, "") + '|'  # 除去最大公共前缀后剩余部分
                    x = depart[0] + '\'' + '->' + x
                    x = x.strip('|')  # 去除末尾的|符号
                    result_2.append(x)  # 添加到结果列表中
                # print("x:", x)
        # print("depart: ", depart[0])


def list2str(l: list):
    string = ""
    for i in l:
        string += (str(i) + "")
    return string


def isN(c):
    """
    是否为非终结符
    :param c:
    :return:
    """
    if c in N:
        return True
    else:
        return False


def isT(c):
    """
    是否为终结符
    :param c:
    :return:
    """
    if c in T or c.isdigit():
        return True
    else:
        return False


# 初始化 first 集 和follow集合字典的键值对中的 值 为空
def init():
    """
    初始化first和follow集合
    :return:
    """
    for str in sentences:
        part_begin = str.split("->")[0]
        part_end = str.split("->")[1]
        FIRST[part_begin] = set()
        FOLLOW[part_begin] = set()
    FOLLOW[S].add('#')  # '#将#加入起始符的FOLLOW集中


# 求一个字符的FIRST集
def f(c):
    if isN(c):
        # print("FIRST[c]",FIRST[c])
        return FIRST[c]
    else:
        s = set()
        s.add(c)
        return s


def error():
    print("error")


# 求一个字符串的FIRST集 A1A2A3....
def ff(s):
    first = set()

    temp = set()
    offset=""
    if len(s)>=2 and s[1]=="'":
        i = 2
        offset="'"
    else:
        i=1
    temp = temp | f(s[0]+offset)
    temp.discard('ε')  # 删除空
    first = first | temp
    # 有推得空串的字符，下一个字符的first需要添加到这个串的first集合中
    first_b=first # 前一个字符的first集合
    # 遍历剩余串
    while "ε" in first_b and i < len(s):
        t = set()
        if i+1<len(s) and s[i+1]=="'":
            t = t | FIRST[s[i]+s[i+1]]
            t.discard('ε')
            first = first | t  # 没有推得空串的时候需要加上去
            i += 2
        else:
            t = t | FIRST[s[i]]
            t.discard('ε')
            first = first | t  # 没有推得空串的时候需要加上去
            i += 1

    # 所有都含有epsilon
    if i == len(s) and s[i-1]!="'" and 'ε' in f(s[i - 1]):
        first.add('ε')
    if i == len(s) and s[i-1]=="'" and 'ε' in f(s[i - 2]+"'"):
        first.add('ε')
    # print("FIRST(s)=",first)
    return first


def getFirst():
    """
     对文法中产生式左部求first集合
    :return:
    """

    # X->a X->ε 第一种情况
    def getFirst_1():
        """
        X->a X->ε
        :return:
        """
        while 1:
            test = FIRST
            for str in sentences:
                part_begin = str.split("->")[0]
                part_end = str.split("->")[1]
                if part_end[0] in T:  # ->号右边的第一个字符是终结符
                    FIRST[part_begin].add(part_end[0])
            if test == FIRST:  # 不再变化就结束
                break;
        # print(FIRST)

    ##求first第二部分 针对 A -> B..型
    def getFirst_2():
        for str in sentences:
            part_begin = str.split('->')[0]
            part_end = str.split('->')[1]
            ##如果型如A ->B 则把B的first集加到A 的first集中去
            if isN(part_end[0]):  # ->右边第一符号是非终结符
                if len(part_end) == 1:  # ->右边只有一个符号，就是非终结符
                    FIRST[part_begin] = FIRST[part_begin] | FIRST[part_end[0]]
                else:
                    temp = set()
                    if part_end[1] == "'":
                        temp = temp | FIRST[part_end[0] + part_end[1]]
                        i = 2
                    else:
                        temp = temp | FIRST[part_end[0]]
                        i = 1
                    temp.discard('ε')
                    FIRST[part_begin] = FIRST[part_begin] | temp
                    while ('ε' in f(part_end[i - 1])) and i < len(part_end):
                        t = set()
                        if part_end[i + 1] != "'":
                            t = t | FIRST[part_end[i]]
                            t.discard('ε')
                            FIRST[part_begin] = FIRST[part_begin] | t
                            i += 1
                        else:
                            t = t | FIRST[part_end[i] + part_end[i + 1]]
                            t.discard('ε')
                            FIRST[part_begin] = FIRST[part_begin] | t
                            i += 2
                    if i == len(part_end) and 'ε' in f(part_end[i - 1]):
                        FIRST[part_begin].add('ε')

    getFirst_1()
    getFirst_2()

    while 1:
        test = FIRST.copy()
        getFirst_2()
        if test == FIRST:
            break
    for key, value in FIRST.items():
        print("First({0})={1}".format(key, value))


def getFOLLOW():
    """
     对文法中产生式左部求follow集合
    :return:
    """

    def getFollow_1():
        for str in sentences:
            part_begin = str.split("->")[0]
            part_end = str.split("->")[1]
            i = 0
            while i < len(part_end):
                e = part_end[i]
                if isN(e) and i + 1 < len(part_end) and part_end[i + 1] == "'":
                    if i + 1 != len(part_end) - 1:
                        temp = set()
                        temp = temp | ff(part_end[i + 2:])
                        if 'ε' in temp:
                            FOLLOW[e] = FOLLOW[e] | FOLLOW[part_begin]
                        # else:
                        temp.discard('ε')
                        FOLLOW[e] = FOLLOW[e] | temp
                        i += 2
                    else:
                        FOLLOW[e + "'"] = FOLLOW[e + "'"] | FOLLOW[part_begin]
                        i += 2
                elif isN(e):
                    if i != len(part_end) - 1:  # 不是->右边最后一个A->aBβ
                        # temp为β的first集
                        temp = set()
                        # print(part_end[i+1:],ff(part_end[i + 1:]))
                        temp = temp | ff(part_end[i + 1:])
                        if 'ε' in temp:
                            FOLLOW[e] = FOLLOW[e] | FOLLOW[part_begin]
                        # else:
                        temp.discard('ε')
                        FOLLOW[e] = FOLLOW[e] | temp
                    else:
                        FOLLOW[e] = FOLLOW[e] | FOLLOW[part_begin]
                    i+=1
                else:
                    i+=1
                    pass
    getFollow_1()
    while 1:
        test = FOLLOW.copy()
        getFollow_1()
        if test == FOLLOW:
            break
    for key, value in FOLLOW.items():
        print("FOLLOW({0})={1}".format(key, value))


def LL1():
    """
    LL语法分析
    :return:
    """
    global buffer
    new_grammar = []

    # # 用户输入文法，程序读入
    # grammar = read_grammar()
    # grammar=["E->E+T|T","T->T*F|F","F->(E)|-F|i"]
    # grammar = ["L->E;L|ε", "E->E+T|E-T|T", "T->T*F|T/F|T%F|F", "F->(E)|i|n"]
    grammar = ["S->aABe", "A->b|Abc", "B->d"]
    # 判断左递归，并返回结果
    print("\n判断过程：")
    judge_result(grammar)
    # 打印消除左递归后的结果
    print("\n消除左递归后的结果为：")

    for each in result_1:
        print(each)
    # 提取左因子
    get_left_factor(result_1)

    print("\n提取左因子后的结果为：")
    for each in result_2:
        print(each)
        production = each.split('->')
        left = production[0]
        right = production[1]
        right_list = right.split('|')
        for i in right_list:
            new_grammar.append((left + '->' + i).strip(' '))
            sentences.append((left + '->' + i).strip(' '))

    # sentences=["T->FT","T'->*FT'|ε",'F->(E)|-F|i','S->aAd|aBe']
    global S
    S = sentences[0].split('->')[0]
    # 提取终结符和非终结符
    epsilon_flag = 0
    for i in sentences:
        if 'ε' in i:
            epsilon_flag = 1
        s = i.split('->')
        for k in s:
            for j in range(len(k)):
                if k[j].isupper():
                    if j + 1 < len(k) and k[j + 1] == "'":
                        N.add(k[j] + k[j + 1])
                    else:
                        N.add(k[j])
                elif k[j].islower():
                    T.add(k[j])
                elif k[j] not in "'":
                    T.add(k[j])
                else:
                    pass
    if epsilon_flag:
        T.add('ε')
    T.add('#')
    print("文法起始符号:", S)
    print("终结符:", T)
    print("非终结符:", N)
    print("LL(1)预测分析：")
    init()
    # 求first集合和follow集合
    getFirst()
    getFOLLOW()
    table = dict()

    # 构造预测分析表
    def formTable():
        # 初始化预测分析表
        nonlocal table
        for n in N:
            temp = dict()
            for t in T:
                temp.setdefault(t, '')
            table.setdefault(n, temp)

        # 构造预测分析表
        for each in sentences:
            left = each.split("->")[0]
            right = each.split("->")[1]
            for t in ff(right):
                table[left][t] = each
            if 'ε' in ff(right):
                for b in FOLLOW[left]:
                    table[left][b] = each
        table_df = pd.DataFrame(np.zeros([len(N), len(T)], dtype=object))
        table_df.index = N
        table_df.columns = T
        print(table)
        for i in N:
            for j in T:
                table_df.loc[i][j] = table[i][j]
        pt = PrettyTable()
        cols = table_df.columns
        pt.field_names = table_df.columns
        pt.add_rows(table_df.values)
        pt.add_column(' ', np.array(list(N)))
        print(pt)
        # 打印预测分析表
    # 构造预测分析程序
    def analyze():
        stack = ['#', S]  # 列表尾是栈顶 ,S 是文法起始符号
        buf = buffer + '#'
        p = 0  # 输入指针
        # print("步骤\t\t 栈内容\t\t\t\t\t 当前输入\t 动作")
        step = 1
        analyze_table = []
        while 1:
            X = stack[-1]  # 栈顶
            a = buf[p]
            temp = ['(' + str(step) + ')', list2str(stack), list2str(buf[p:])]
            if isT(X) or X == '#':
                if a.isdigit():  # 只包含数字
                    a = 'i'
                if X == a:
                    pol = stack.pop()
                    p = p + 1
                    # 处理撇号
                    if pol=="'":
                        t=stack.pop()
                        pol=t+pol
                    temp.append('pop(\'' + str(pol) + '\'),next(ip)')
                else:
                    temp.append("error")
                    analyze_table.append(temp)
                    # error()
                    print("error1")
                    break
            elif isN(X) or X=="'":  # X是非终结符
                if X=="'":
                    stack.pop()
                    X=stack[-1]+"'"
                if a.isdigit():
                    a = 'i'
                if a=="#" and len(stack)>1:
                    # print("出错，栈不为# 此时串已经分析完毕")
                    if table[stack[-1]][a]==stack[-1]+'->ε':
                        # 按空情况
                        # temp.append("pop("+stack[-1]+"),按"+stack[-1]+"->ε展开")
                        # stack.pop()
                        # analyze_table.append(temp)
                        # continue
                        pass
                    else:
                        temp.append("error")
                        analyze_table.append(temp)
                        break
                sen = table[X][a]
                if sen != '':  # 查表发现相应位置不为空
                    string = sen.split("->")[1]
                    if string == 'ε':
                        poll = stack.pop()
                        temp.append('pop(' + str(poll) + ')'+",按"+X+"->ε展开")
                    else:
                        rev = string[::-1]  # 反转
                        poll = stack.pop()
                        if poll=="'":
                            poll=stack.pop()+poll
                        rev=list(rev)
                        for i in range(len(rev)):
                            if rev[i]=="'":
                                rev[i+1]+=rev[i]
                        if "'" in rev:
                            rev.remove("'")
                        stack.extend(rev)
                        temp.append('pop(' + str(poll) + '),push(' + string + ')'+',按'+poll+'->'+string+'展开')
                else:
                    # error()
                    temp.append("error")
                    analyze_table.append(temp)
                    print("error2")
                    break
            # print("stack=", stack)
            step += 1
            analyze_table.append(temp)
            if X == '#':
                break
        analyze_table = pd.DataFrame(np.array(analyze_table))
        analyze_table.columns = ['步骤', '栈内容', '当前输入', '动作']
        pd.set_option('display.unicode.ambiguous_as_wide', True)
        pd.set_option('display.unicode.east_asian_width', True)
        pd.set_option('display.width', 100)  # 设置打印宽度(**重要**)
        pt = PrettyTable()
        pt.field_names = analyze_table.columns
        pt.add_rows(analyze_table.values)
        print(pt)
        # if a == "#" and len(stack) > 1:
        #     print("出错，栈不为#。此时串已经分析完毕，字符串不合法")

    print("\t" * 7 + "预测分析表")
    formTable()
    print()
    while True:
        buffer=input("输入测试字符串(输入退出结束测试):")
        # analyze()
        if buffer=="退出":
            break
        print("\t" * 7 + "分析步骤")
        analyze()


buffer = 'abbcd'  # 待分析的字符串
LL1()
